# 动态规划 最大子乘积
def maxProduct(nums):
    if nums is None:
        return 0
    # 生成二维数组
    dp = [[0 for _ in range(2)] for _ in range(2)]
    # 之前最大的，和之前最小的乘积，res是最终结果
    dp[0][1], dp[0][0], res = nums[0], nums[0], nums[0]

    for i in range(1, len(nums)):
        x, y = i % 2, (i - 1) % 2
        dp[x][0] = max(dp[y][0] * nums[i], dp[y][1] * nums[i], nums[i])
        dp[x][1] = min(dp[y][0] * nums[i], dp[y][1] * nums[i], nums[i])
        res = max(res, dp[x][0])
        print(dp, "x:", x, " y:", y, " res:", res, " nums[i]:", nums[i])
    return res


# 第二种写法
def maxProduct2(nums):
    if nums is None:
        return 0
    res, curMax, curMin = nums[0], nums[0], nums[0]
    for i in range(1, len(nums)):
        num = nums[i]
        curMax, curMin = curMax * num, curMin * num
        curMin, curMax = min(curMax, curMin, num), max(curMax, curMin, num)
        res = curMax if curMax > res else res
    return res


if __name__ == '__main__':
    print("result:", maxProduct([2, 3, -2, 4]))
    print("result:", maxProduct2([2, 3, -2, 4]))
